package org.example.everyday;


import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/second-minimum-time-to-reach-destination/
 */

public class SecondMinimum {
    protected static final Logger logger = LoggerFactory.getLogger(SecondMinimum.class);

    public static void main(String[] args) {
        //声明是5个节点
        int  n = 5;
        //声明5个边的路径
        int[][] edges = new int[][]{{1,2},{1,3},{1,4},{3,4},{4,5}};
        //time是每个边的路长，change是标明红绿灯多长时间变换一次
        int time = 3, change = 5;

        int result = secondMinimum(n,edges,time,change);
        System.out.println("第2短的时间是："+result);
    }

    /**
     * 用广度优先遍历实现求第二短的长度
     * @param n 声明是几个定点
     * @param edges 几个边
     * @param time 走完每一个边的长度
     * @param change 红绿灯的变换时间
     * @return
     */
    public static int secondMinimum(int n,int[][] edges,int time,int change){
        //定义一个图
       List<Integer>[] graph = new List[n+1];
       for (int i=0;i<=n;i++){
           //初始化数据
           graph[i] = new ArrayList<Integer>();
       }
       //循环生成图形 上下衔接关系
       for (int[] edge:edges){
           graph[edge[0]].add(edge[1]);
           graph[edge[1]].add(edge[0]);
       }

       //定义从1到i的path最短路径和  次短路径
       int[][] path = new int[n+1][2];
       for (int i=0;i<=n;i++){
           Arrays.fill(path[i],Integer.MAX_VALUE);
       }
       path[1][0] = 0;

       Queue<int[]> queue = new ArrayDeque<int[]>();
       queue.offer(new int[]{1,0});

       while (path[n][1] == Integer.MAX_VALUE){
           int[] arr = queue.poll();
           int cur = arr[0],len = arr[1];
           for (int next:graph[cur]){
               if(len+1 < path[next][0]){
                   path[next][0] = len + 1;
                   queue.offer(new int[]{next,len + 1});
               }else if(len+1 > path[next][0] && len+1<path[next][1]){
                   path[next][1] = len+1;
                   queue.offer(new int[]{next,len+1});
               }
           }
       }

       int ret = 0;
       for (int i = 0;i<path[n][1];i++){
           if(ret%(2*change)>change){
               ret = ret + (2*change - ret%(2*change));
           }
           ret +=time;
       }
        return ret;
    }

}
